//
// Created by Rory on 2020/10/9.
//

#ifndef DATA_STRUCTURE_PROGRAMMING_USING_C_LINKEDLIST_H
#define DATA_STRUCTURE_PROGRAMMING_USING_C_LINKEDLIST_H

#include "../common.h"
/*
 * 单链表
 */
#ifndef NODE_ELEMENT_TYPE
#define NODE_ELEMENT_TYPE int
#endif

typedef struct Node {//结点结构体
    NODE_ELEMENT_TYPE data;
    struct Node* next;
}* Node;

struct SingularLList;

typedef struct{ //带头节点的单链表结构体
    Node head;
    size_t length;

    /*
     * 基本操作
     */
    //后插
    bool (*InsertBehind) (struct SingularLList* list, Node node, NODE_ELEMENT_TYPE element);
    //位序插入
    bool (*Insert) (struct SingularLList* list, int location, NODE_ELEMENT_TYPE element);
    //追加操作
    bool (*Append) (struct SingularLList* list, NODE_ELEMENT_TYPE element);
    //前插
    bool (*InsertFront) (struct SingularLList* list, Node node, NODE_ELEMENT_TYPE element);
    //按位序删除
    bool (*Delete) (struct SingularLList* list, int location, NODE_ELEMENT_TYPE* element);
    //销毁链表
    void (*Destroy) (struct SingularLList* list);

}SingularLList;




static bool InsertBehind (SingularLList* list, Node p, NODE_ELEMENT_TYPE element){
    if(!p && !list){
        return false;
    }

    Node node = malloc(sizeof(Node));//创建结点
    if(!node){
        return false;
    }
    node->data = element;

    node->next = p->next;//插入结点
    p->next = node;

    list->length++;

    return true;
}

static bool Insert (SingularLList* list, int location, NODE_ELEMENT_TYPE element){
    if(list == NULL || location < 1 || location > list->length+1){//判断location的合法性
        return false;
    }

    Node p = list->head;
    for (int i = 0; i < location-1 && p != NULL; p = p->next,i++);//找到插入位置的前一个结点

    return InsertBehind(list, p, element);
}

static bool LinkedAppend (SingularLList* list, NODE_ELEMENT_TYPE element){
    return Insert(list,list->length+1,element);
}

//实现方式：前插转后插
static bool InsertFront (SingularLList* list, Node p, NODE_ELEMENT_TYPE element){
    if(!p && !list){
        return false;
    }

    Node temp = list->head;
    while (temp != NULL && temp->next != p){//找到node结点的前驱结点
        temp = temp->next;
    }

    return InsertBehind(list, temp, element);
}

static bool Delete (SingularLList* list, int location, NODE_ELEMENT_TYPE* element){
    if(list == NULL || location < 1 || location > list->length || element != NULL){//判断location的合法性
        return false;
    }

    Node p = list->head;
    for (int i = 0; i < location-1 && p != NULL; p = p->next,i++);//找到删除位置的前一个结点

    *element = p->next->data;//返回数据

    Node deleted = p->next;
    p->next = p->next->next; //p->next would never be 'NULL', so don't be afraid.
    list->length--;
    free(deleted);
}

static void DestroyLinkedList(SingularLList* list){
    if(!list){
        return;
    }
    Node p = list->head;
    Node deleted = NULL;
    while (p!=NULL){
        deleted = p;
        free(deleted);
        p = p->next;
    }
}

bool InitSingularLList(SingularLList* list){
    /**
     * 1. 初始化头节点
     * 2. 初始化函数指针
     */
    if(list == NULL){
        return false;
    }
    list->length = 0;
    list->head = malloc(sizeof(Node));
    list->head->next = NULL;

    list->InsertBehind = InsertBehind;
    list->Insert = Insert;
    list->Append = LinkedAppend;
    list->InsertFront = InsertFront;
    list->Delete = Delete;
    list->Destroy = DestroyLinkedList;
}

//删除不带头节点的单链表中所有值为e的结点
/*SingularLList原本被设计为带头节点的单链表，但这个函数对带不带头节点都适用。pre参数一般传入head指针*/
/*调用范例:删除 (头节点)->4->3->4->NULL 这个链表值为4的结点
 * 1. 创建
    SingularLList list;
    InitSingularLList(&list);
    singularLList.Append(&list,4);
    singularLList.Append(&list,3);
    singularLList.Append(&list,4);
 * 2. 调用
    DeleteElementRecusively(&list,list->head,list->head->next);
 * */
void DeleteElementRecursively(SingularLList* list, Node start, NODE_ELEMENT_TYPE e){
    Node current = start->next;
    if(current == NULL){
      return;
    }
    if(current->data == e){
      start->next = current->next;
      free(current);
      list->length--;
      DeleteElementRecursively(list, start, e);
    }else{
      DeleteElementRecursively(list, current, e);
    }
}

/*
 * 递归反向输出元素的值
*/
void IntPrintConverselyRecursively(const Node p){
    if(p!=NULL) {
        IntPrintConverselyRecursively(p->next);
        printf("%d ",p->data);
    }
}

/*
 * 递归正向输出元素的值
*/
void IntPrintRecursively(Node p){
    if(p!=NULL) {
        printf("%d ",p->data);
        IntPrintRecursively(p->next);
    }
}

/**
 * 逆置链表(头节点也将被逆置为尾结点)
 */
SingularLList ReverseSingularList(SingularLList* list){
    Node current = list->head->next;//第一个结点(非头节点)
    list->head->next = NULL;//头节点转为最后一个节点
    Node next = NULL;

    //前插法依次逆置（创建）链表。实质就是前插法创建链表，只不过没有创建新结点而已
    while (current!=NULL){
        next = current->next;//防止断链

        current->next = list->head;
        list->head = current;

        current = next;//移动到下一个待前插的结点
    }

    return *list;
}
#endif //DATA_STRUCTURE_PROGRAMMING_USING_C_LINKEDLIST_H
